package com.aikon.wht.paoshan;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author WANGHAITAO273
 */
public class PaoshanOfLRU {

    // 缓存淘汰策略：FIFO（先入先出），LFU（最少使用），LRU（最近最少使用）


    // 一般实现思路：维护一个有序单链表，获取数据时，若已在链表中，则删除节点，重新添加到链表尾，若不在链表中，链表已满，则删除链表头，添加到链表尾，链表未满，直接添加到链表尾

    // LRU最简单方法： 用LinkedHashMap#removeEldestEntry实现删除最长寿命key，构造LinkedHashMap时accessOrder=true(所有entry按访问顺序排列).
    // LinedHashMap.Entry除了维护一个next记录在桶中链表中的位置外，LinkedHashMap.Entry比HashMap.Entry多维护了一个before和after属性，用于记录其插入或访问顺序。

    /**
     * 用linkedHashMap实现LRU缓存
     *
     * @param <K>
     * @param <V>
     */
    public static class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private int capacity;

        public LRUCache(int capacity) {
            super(16, 0.75f, true);
            this.capacity = capacity;
        }


        @Override
        protected boolean removeEldestEntry(Map.Entry entry) {
            return this.size() > capacity;
        }
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> lruCache = new LRUCache(5);
        lruCache.put("a", 1);
        lruCache.put("b", 2);
        lruCache.put("c", 3);
        lruCache.put("d", 4);
        lruCache.put("e", 5);
        lruCache.get("a");
        lruCache.entrySet().stream().forEach(i -> System.out.println(i.getValue()));
        lruCache.put("f", 6);
        lruCache.entrySet().stream().forEach(i -> System.out.println(i.getValue()));
    }

}
